#include<iostream>
#include<vector>
using namespace std;

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n));

    int begin = 0, end = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j])
                dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
            if (dp[i][j] && j - i >= end - begin) {
                begin = i;
                end = j;
            }
        }
    }

    return s.substr(begin, end - begin + 1);
}


int main()
{
    string s = "aQwQrqq";
    cout << longestPalindrome(s) << endl;
    return 0;
}